﻿// 358 岛屿.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>

using namespace std;


/*
* 
* https://www.acwing.com/problem/content/360/
* 
你准备游览一个公园，该公园由 N 个岛屿组成，当地管理部门从每个岛屿出发向另外一个岛屿建了一座桥，不过桥是可以双向行走的。

同时，每对岛屿之间都有一艘专用的往来两岛之间的渡船。

相对于乘船而言，你更喜欢步行。

你希望所经过的桥的总长度尽可能的长，但受到以下的限制：

可以自行挑选一个岛开始游览。
任何一个岛都不能游览一次以上。
无论任何时间你都可以由你现在所在的岛 S 去另一个你从未到过的岛 D。由 S 到 D 可以有以下方法：
（1）步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离中。
（2）渡船：你可以选择这种方法，仅当没有任何桥和以前使用过的渡船的组合可以由 S 走到 D
（当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛）。
注意，你不必游览所有的岛，也可能无法走完所有的桥。

请你编写一个程序，给定 N 座桥以及它们的长度，按照上述的规则，计算你可以走过的桥的最大长度。

输入格式
第 1 行包含整数 N。

第 2..N+1 行，每行包含两个整数 a 和 L，第 i+1 行表示岛屿 i 上建了一座通向岛屿 a 的桥，桥的长度为 L。

输出格式
输出一个整数，表示结果。

对某些测试，答案可能无法放进 32−bit 整数。

数据范围
2≤N≤106,
1≤L≤108
输入样例：
7
3 8
7 2
4 2
1 4
1 9
3 4
2 3
输出样例：
24
*/


#include <iostream>
#include <cstring>
#include <algorithm>

using  namespace std;

typedef long long LL;
const int N = 1200010, M = N * 2;
int n;
int  h[N], e[M], w[M], ne[M], idx;
int fu[N], fw[N]; 
int q[N];
bool st[N], ins[N];
int cir[N], ed[N], cnt;
LL s[N], d[N * 2], sum[N * 2];
LL ans;
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs_c(int u, int from) {
	st[u] = ins[u] = true;

	for (int i = h[u]; ~i; i = ne[i]) {
		if (i == (from ^ 1)) continue;
		int j = e[i];
		fu[j] = u, fw[j] = w[i];
		if (!st[j]) dfs_c(j,i);
		else if (ins[j]) {
			cnt++;
			ed[cnt] = ed[cnt - 1];
			LL sum = w [i]; 
			for (int k = u; k != j; k = fu[k]) {
				s[k] = sum;
				sum += fw[k];
				cir[++ed[cnt]] = k;
			}
			s[j] = sum, cir[++ed[cnt]] = j; 
		}
	}

	ins[u] = false;
}

LL dfs_d(int u) {
	st[u] = true;
	LL d1 = 0; LL d2 = 0;
	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		if (st[j]) continue; 
		LL dist = dfs_d(j) + w[i];
		if (dist >= d1) d2 = d1, d1 = dist;
		else if (dist > d2) d2 = dist;
	}
	ans = max(ans, d1 + d2);

	return d1;
}


int main()
{
	scanf("%d",&n);
	memset(h,-1,sizeof h);

	for (int i = 1; i <= n; i++) {
		int a, b;
		scanf("%d%d",&a,&b);
		add(i, a, b); add(a, i, b);
	}

	for (int i = 1; i <= n; i++) {
		if (!st[i]) {
			dfs_c(i, -1);
		}
	}

	memset(st, 0, sizeof st);
	for (int i = 1; i <= ed[cnt]; i++) st[cir[i]] = true;

	LL res = 0;
	for (int i = 1; i <= cnt; i++) {
		ans = 0; int sz = 0;
		for (int j = ed[i - 1] + 1; j <= ed[i]; j++) {
			int k = cir[j];
			d[sz] = dfs_d(k);
			sum[sz] = s[k];
			sz++;
		}
		for (int j = 0; j < sz; j++) { d[sz + j] = d[j], sum[sz + j] = sum[j] + sum[sz - 1]; }

		int hh = 0; int tt = -1;
		for (int j = 0; j < sz*2; j++) {
			if (hh <= tt && j - q[hh] >= sz) { hh++;}
			if (hh <= tt) ans = max(ans,d[j]+sum[j] + d[q[hh]]-sum[q[hh]]);
			while (hh <= tt && d[q[tt]] - sum[q[tt]] <= d[j] - sum[j]) tt--;
			q[++tt] = j;
		}
		res += ans;
	}

	printf("%lld\n",res);
	return 0;
}

 